package main

import (
	"fmt"

	"local/datastructure/queue"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	root := generateTree()

	fmt.Print("前序遍历:")
	preOrder(root)

	fmt.Print("中序遍历")
	midOrder(root)

	fmt.Print("后序遍历")
	tailOrder(root)

	fmt.Print("层序遍历")
	levelOrder(root)
}

func preOrder(root *TreeNode) {
	if root == nil {
		return
	}

	fmt.Print(root.Val)
	preOrder(root.Left)
	preOrder(root.Right)
}

func midOrder(root *TreeNode) {
	if root == nil {
		return
	}

	preOrder(root.Left)
	fmt.Print(root.Val)
	preOrder(root.Right)
}

func tailOrder(root *TreeNode) {
	if root == nil {
		return
	}

	tailOrder(root.Left)
	tailOrder(root.Right)
	fmt.Print(root.Val)
}

func levelOrder(root *TreeNode) {
	if root == nil {
		return
	}
	q := queue.NewQueue()
	q.Push(root)
	for !q.IsEmpty() {
		node, _ := q.Pop()
		curr := node.(*TreeNode)
		fmt.Print(curr.Val)
		if curr.Left != nil {
			q.Push(curr.Left)
		}

		if curr.Right != nil {
			q.Push(curr.Right)
		}
	}
}

func generateTree() *TreeNode {
	n1 := TreeNode{Val: 1}
	n2 := TreeNode{Val: 2}
	n3 := TreeNode{Val: 3}
	n1.Left = &n2
	n1.Right = &n3
	return &n1
}
